import java.io.File;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;


public class ReplacementSelection {

	private int runCounter = 1; // # run
	private int[] intHeap; // lijst waarin we gaan werken
	private int next;
	private boolean runDone = false; // bijhouden of je een run klaar is
	private boolean totalDone = false; // bijhouden of je helemaal klaar bent

	private Heap<Integer> heap; // Instantie van de klasse Heap
	private int nextIndex = Heap.getHeapSize(); // Bijhouden welke index je
												// bent.
	private ArrayList<Integer> deadList; // Een kleine tijdelijke lijst die de
											// waardes in de deadspace bijhoudt.
	private ArrayList<Integer> runIntList; // houd de lijst met int's bij per
											// run

	public ReplacementSelection(int[] reeks) throws IOException {

		createRuns(reeks);

	}

	public void createRuns(int[] reeks) throws IOException {

		runIntList = new ArrayList<Integer>();
		ArrayList<Integer> temp = new ArrayList<Integer>(); // deze lijst met
															// int's voeg je
															// later toe aan de
															// heap
		deadList = new ArrayList<Integer>();

		intHeap = reeks;
		int last = Heap.getHeapSize(); // pointer naar de laatste index in de heap
		

		for (int i = 0; i < Heap.getHeapSize(); i++) { 
			// voeg de eerste #H-aantal elementen toe aan de heap
			temp.add(reeks[i]);
			// en verwijder deze entries uit intList
			reeks[i] = -1; 
		}

		int tmpSize = (sizeFull(intHeap));
	
		int[] tmp = new int[tmpSize];
		for (int j = 0; j < tmpSize; j++) {
			if (intHeap[j] != -1) { 
				tmp[j] = intHeap[j]; 
			}
		}

		// je blijft wel 0's overhouden, want vaste lengte, daar
		// moet dus overheen gelezen worden
		intHeap = tmp; 

		
		heap = new Heap<Integer>(temp); // build the heap (already sorted)

		// keep iterating untill you have had all the elements
		while (!isEmpty(intHeap) && last > -1 || !totalDone) {

			next = getNext(intHeap); 
			
			System.out.println("---> NEXT: " + next);
			
			// if next is larger than out, we can add it to the heap
			if (next >= heap.element()) {
				deleteMin();
				heap.add(next);
				setNullIndex(next);
				System.out.println(runIntList + "OUT");
				System.out.println("heap new " + heap);
			} else {
				deleteMin();
				
				// heap[0] = last
				heap.setValueToIndex(heap.getValueFromIndex(last), 0); 
				
				// heap[last] = next
				heap.setValueToIndex(next, last); 
				deadList.add(next);
				
				last--; 
				
				// set pointer to deadspace
				heap.setDeadSpace(last); 
				
				if ((heap.getDeadSpacePointer()) >= 1) {
					//percolate down for every element BEFORE wehere the DeadSpacepointer is
					heap.percolateDown(heap.getDeadSpacePointer() - 1); 
					System.out.println("heap after deadspace " + heap);
				} else {
					//Anders is er een run klaar
					runDone = true;
				}
			}
		
		
			if (runDone) {				
				writeOut(runIntList);
				runCounter++;				
				clearList();
				runDone = false;
				last = Heap.getHeapSize();
				heap.addAll(deadList);
				deadList.clear();
			}
			
			if (totalDone) {
				
				heap.percolateDown(Heap.getHeapSize() - 1);
				for (int i : heap) {
					runIntList.add(i);
				}
				
				writeOut(runIntList);
				runCounter++;
				writeOut(deadList);
				clearList();
				
				//Dit is het einde:
				break;
			}

			//Voor een mooiere output
			System.out.println("");
			System.out.println("");
		}

	}

	
	public void setNullIndex(int value) {

		for (int i = 0; i < intHeap.length - 1; i++) {
			if (intHeap[i] == value) {
				intHeap[i] = 0;
				break;
			}
		}
	}

	/**
	 * Write the smallest element in the Heap to the output tape. Read the next
	 * element from the input put. If it is larger than the element just
	 * written, we can add it to the Heap; otherwise, it cannot go into the
	 * current run, and thusfully been put into the 'deadspace'.
	 */
	public int deleteMin() {
		int minItem = (Integer) heap.remove();
		runIntList.add(minItem);
		return minItem;
	}

	public void clearList() {
		runIntList.clear();
	}

	public boolean isEmpty(int[] list) {
		boolean result = true;
		for (int i = 0; i < list.length;) {
			if (list[i] == 0) {
				i++;
			} else if (list[i] != 0) {
				i++;
				result = false;
				return result;
			}
		}
		return result;
	}

	
	public void writeOut(ArrayList<Integer> run) throws IOException {
		PrintWriter pw = null;
		File f = new File("outFile.txt");

		try {
			pw = new PrintWriter(new FileOutputStream(f, true));
			
			pw.println("Run: " + runCounter);
			pw.println("------------------");
			for (int i = 0; i < run.size(); i++) {
				pw.println(run.get(i));
			}
			pw.println("End of Run");
			pw.println("------------------");

			System.out.println(run + " weggeschreven");
		} catch (IOException e) {
			e.printStackTrace();
		} finally {
			pw.close();
		}
	}

	public int getNext(int[] heap) {
		if (nextIndex == heap.length - 1 && !isEmpty(intHeap)) {
			totalDone = true;
		}
		
		nextIndex++;
		return heap[nextIndex - 1];
	}

	/**
	 * Returns the size of intList excluding 0's
	 * 
	 * @return
	 */
	public int sizeFull(int[] array) {
		int result = 0;

		for (int i : array) {
			if (i != 0) {
				result++;
			}
		}

		return result;
	}

}
